/* mem.c : memory manager
 */

#include <kernel.h>
#include <i386.h>

typedef struct memHeader{		/* Memory header, used to track memory extent length */
					/*	and prev/next free blocks if in free list   */
	unsigned long size;	 	/* Free space starting at dataStart/end of header   */
	struct memHeader* prev;		/* Previous free block, or NULL if none exists      */
	struct memHeader* next;		/* Next free block, or NULL if none exists	    */
	char* sanityCheck;		/* Set to the same value as size on allocation, and set */
					/*	to zero on memory free. Used by kfree()		*/
	unsigned char dataStart[0];	/* Used to reference the first byte after the head, */
					/* 	the start of useable allocated memory		*/
}memHeader;

memHeader* memStart;
extern long freemem;
/*
*	Initializes memHeader structures around memory available to processes. (From extern long
*		freemem to HOLESTART and from HOLEEND to 0x400000)
*/
extern void kmeminit(void){
	//kprintf("freemem: %d\n", freemem);
	memStart = (memHeader*)freemem;
	unsigned long aligned_size = HOLESTART-freemem-sizeof(memHeader);
	if((aligned_size%16)){
		//kprintf("Before hole size not multiple of 16 (%d) resizing\n", aligned_size);
		aligned_size = ((aligned_size/16)*16);
		//kprintf("Size is now: %d\n", aligned_size);
	}
	memStart->size = aligned_size;
	memStart->next = (memHeader*)HOLEEND;
	memStart->prev = (memHeader*)NULL;
	memHeader* afterHole = (memHeader*)HOLEEND;
	aligned_size = 0x400000-HOLEEND-sizeof(memHeader);
	if((aligned_size%16)){
		//kprintf("After hole size not multiple of 16 (%d) resizing\n", aligned_size);
		aligned_size = ((aligned_size/16)*16);
		//kprintf("Size is not: %d\n", aligned_size);
	}	
	afterHole->size = aligned_size;
	afterHole->next = (memHeader*)NULL;
	afterHole->prev = memStart;
}
/*
*	Allocates physical memory of size size, and returns a pointer to it if enough space
*		is available. Otherwise returns 0.
*/
extern void *kmalloc(int size){
	if(size<=0){
		//kprintf("Invalid size requested: %d. Size must be greater than 0\n", size);
		return 0;
	}	
	int aligned_size = (size)/16 + ((size%16)?1:0);
	aligned_size = aligned_size*16 + sizeof(memHeader);
	memHeader* curr = memStart;
	if(!curr){
		//kprintf("ERROR: Out of Memory - see mem.c kmalloc\n\n");
		return 0;
	}
	while(1){
		if(curr->size >= aligned_size) break;
		if(!curr->next) return 0;
		curr = curr->next;
	}
	memHeader* kmmem = curr;
	kmmem->sanityCheck = kmmem->dataStart;
	if(kmmem->size == aligned_size){
		////kprintf("found block of size: %d at %d\n", kmmem->size, kmmem);
		if(kmmem->prev) kmmem->prev->next = kmmem->next;
		else memStart = kmmem->next;
		if(kmmem->next) kmmem->next->prev = kmmem->prev;
	}
	else{
		memHeader* leftOverHeader =(memHeader*)(((int)kmmem)+aligned_size);
		leftOverHeader->size = kmmem->size-aligned_size;
		leftOverHeader->prev = kmmem->prev;
		leftOverHeader->next = kmmem->next;
		if(kmmem->prev) kmmem->prev->next = leftOverHeader;
		else memStart = leftOverHeader;
		if(kmmem->next) kmmem->next->prev = leftOverHeader;
		////kprintf("Split off block of size: %d at %d, left size %d at %d\n", aligned_size, kmmem, leftOverHeader->size, leftOverHeader);			
	}
	kmmem->size = aligned_size - sizeof(memHeader);
	return kmmem->dataStart;
}
/*
*	Frees the physical memory pointed at by ptr. Checks pointer to ensure it is a nonzero 
*		value. Also uses sanityCheck as defined in struct memHeader to attempt to prevent
*		incorrectly freeing memory
*/
extern void kfree(void *ptr){
	if((int)ptr <= 0){
		//kprintf("Invalid pointer, %d, pointer must be greater than 0\n", ptr);
		return;
	}
	//kprintf("Freeing mem at: %d\n", ptr);	
	ptr = (void*)(((int)ptr) - sizeof(memHeader));
	memHeader* tofree = (memHeader*)ptr;
	if((long)tofree->sanityCheck != (long)tofree->dataStart){
		//kprintf("ERROR: sanity check mismatch sanityCheck:%d, dataStart:%d\n", tofree->sanityCheck, tofree->dataStart);
		return;
	}
	tofree->sanityCheck = 0; //set it so it wont be accidentally re-freed
	memHeader* curr = memStart;
	if(!curr){
		//kprintf("Tofree is ONLY free block, memStart = tofree\n");
		memStart = tofree;
		tofree->prev = NULL;
		tofree->next = NULL;
		return;
	}
	//kprintf("tofree: %d, tofree->size: %d\n", tofree, tofree->size);
	//kprintf("memstart: %d, memstart->size: %d\n", memStart, memStart->size);	
	while(curr->next && curr < tofree){
		curr = curr->next;
		//kprintf("curr increased to: %d, curr->size: %d, curr->next: %d\n", curr, curr->size, curr->next);
	}
	if(!curr->next && curr < tofree){
		//kprintf("END, ");
		if(((int)curr)+curr->size+sizeof(memHeader) == (int)tofree){
			curr->size += tofree->size;
			curr->size += sizeof(memHeader);
			//kprintf(" curr+=tofree, curr->size: %d, curr->next: %d\n", curr->size, curr->next);
		}	
		else{
			curr->next = tofree;
			tofree->prev = curr;
			tofree->next = NULL;
			//kprintf(" no coalescing\n");
		}	
	}
	else{
		if(curr == memStart){//in this case we also know curr > tofree
			//kprintf("Inserting at head of list,");
			memStart = tofree;
			tofree->prev = NULL;
			if((((int)tofree)+tofree->size+sizeof(memHeader)) == (int)curr){
				tofree->size += curr->size;
				tofree->size += sizeof(memHeader);
				tofree->next = curr->next;
				if(curr->next) curr->next->prev = tofree;	
				//kprintf(" tofree+=curr, tofree->size: %d, tofree->next: %d\n", tofree->size, tofree->next);
			}
			else{
				tofree->next = curr;
				curr->prev = tofree;
				//kprintf(" no coalescing\n");	
			}
		}
		else{
			//kprintf("Inserting in between free blocks, ");
			if((((int)curr->prev)+curr->prev->size+sizeof(memHeader)) == (int)tofree){
				curr->prev->size += tofree->size;
				curr->prev->size += sizeof(memHeader);
				//kprintf(" curr->prev+=tofree, curr->prev->size: %d, curr->prev->next: %d", curr->prev->size, curr->prev->next);
				if((((int)curr->prev)+curr->prev->size+sizeof(memHeader)) == (int)curr){
					//kprintf(" CASCADE, curr->prev+=curr->next, ");
					curr->prev->size += curr->size;
					curr->prev->size += sizeof(memHeader);
					curr->prev->next = curr->next;
					if(curr->next) curr->next->prev = curr->prev;
					//kprintf(" curr->prev->size: %d, curr->prev->next: %d\n", curr->prev->size, curr->prev->next);
				}
				//kprintf("\n");
			}
			else if((((int)tofree)+tofree->size+sizeof(memHeader)) == (int)curr){
				tofree->size += curr->size;
				tofree->size += sizeof(memHeader);
				tofree->prev = curr->prev;
				if(curr->prev) curr->prev->next = tofree;
				tofree->next = curr->next;
				if(curr->next) curr->next->prev = tofree;
				//kprintf(" tofree+=curr, tofree->size: %d, tofree->next:%d\n", tofree->size, tofree->next);
			}
			else{
				//kprintf("NO coalescing\n");
				curr->prev->next = tofree;
				tofree->prev = curr->prev;
				curr->prev = tofree;
				tofree->next = curr;
			}
		}		
	}
}
